{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Connected Components in an Undirected Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countComponents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #无向图中连通分量的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一个包含&nbsp;<code>n</code> 个节点的图。给定一个整数 <code>n</code> 和一个数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示图中&nbsp;<code>a<sub>i</sub></code>&nbsp;和&nbsp;<code>b<sub>i</sub></code>&nbsp;之间有一条边。</p>\n",
    "\n",
    "<p>返回 <em>图中已连接分量的数目</em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/14/conn1-graph.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong><code>n = 5</code>, <code>edges = [[0, 1], [1, 2], [3, 4]]</code>\n",
    "<strong>输出: </strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/14/conn2-graph.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong><code>n = 5,</code> <code>edges = [[0,1], [1,2], [2,3], [3,4]]</code>\n",
    "<strong>输出:&nbsp;&nbsp;</strong>1</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2000</code></li>\n",
    "\t<li><code>1 &lt;= edges.length &lt;= 5000</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>&nbsp;&lt;= b<sub>i</sub>&nbsp;&lt; n</code></li>\n",
    "\t<li><code>a<sub>i</sub>&nbsp;!= b<sub>i</sub></code></li>\n",
    "\t<li><code>edges</code> 中不会出现重复的边</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-connected-components-in-an-undirected-graph](https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-connected-components-in-an-undirected-graph](https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[0,1],[1,2],[3,4]]', '5\\n[[0,1],[1,2],[2,3],[3,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.cot = n\n",
    "\n",
    "    def find(self, x):\n",
    "        while not x==self.parent[x]:\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX==rootY:\n",
    "            return\n",
    "        self.parent[rootX] = rootY\n",
    "        self.cot -= 1\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        for u,v in edges:\n",
    "            uf.union(u, v)\n",
    "        return uf.cot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UF(n)\n",
    "        for edge_pair in edges:\n",
    "            uf.union(edge_pair[0], edge_pair[1])\n",
    "            \n",
    "        return uf.count\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "    \n",
    "    def union(self, p, q):\n",
    "        root_p = self.find(p)\n",
    "        root_q = self.find(q)\n",
    "        if root_p == root_q:\n",
    "            return\n",
    "        self.parent[root_p] = root_q\n",
    "        self.count -= 1\n",
    "    def find(self, x):\n",
    "        while x != self.parent[x]:\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "        # if x != self.parent[x]:\n",
    "        #     self.parent[x] = self.find(self.parent[x])\n",
    "        # return self.parent[x]\n",
    "    def count(self):\n",
    "        return self.count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "        self.cnt = n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootx, rooty = self.find(x), self.find(y)\n",
    "        if rootx != rooty:\n",
    "            if self.rank[rootx] < self.rank[rooty]:\n",
    "                self.parent[rootx] = rooty\n",
    "            elif self.rank[rootx] > self.rank[rooty]:\n",
    "                self.parent[rooty] = rootx\n",
    "            else:\n",
    "                self.parent[rooty] = rootx\n",
    "                self.rank[rootx] += 1\n",
    "            self.cnt -= 1\n",
    "        return \n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        for x, y in edges:\n",
    "            uf.union(x, y)\n",
    "        return uf.cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        for a, b in edges:\n",
    "            uf.union(a, b)\n",
    "        return uf.count\n",
    "    \n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.count = n \n",
    "        self.parents = [i for i in range(n)]\n",
    "    def find(self, x):\n",
    "        while x != self.parents[x]:\n",
    "            self.parents[x] = self.parents[self.parents[x]]\n",
    "            x = self.parents[x]\n",
    "        return x \n",
    "    def union(self, a, b):\n",
    "        root_a, root_b = self.find(a), self.find(b)\n",
    "        if root_a == root_b:\n",
    "            return \n",
    "        self.parents[root_a] = root_b \n",
    "        self.count -= 1\n",
    "    def connected(self, a, b):\n",
    "        root_a, root_b = self.find(a), self.find(b)\n",
    "        return root_a == root_b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "\n",
    "        for edge in edges:\n",
    "            self.union(edge[0], edge[1])\n",
    "        return self.count\n",
    "    \n",
    "    def find(self, x):\n",
    "        while self.parent[x] != x:\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        self.parent[root_x] = root_y\n",
    "        self.count -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.size = [1 for i in range(n)]\n",
    "\n",
    "        for edge in edges:\n",
    "            self.union(edge[0], edge[1])\n",
    "        return self.count\n",
    "    \n",
    "    def find(self, x):\n",
    "        while self.parent[x] != x:\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            self.parent[root_y] = root_x\n",
    "            self.size[root_x] += self.size[root_y]\n",
    "        else:\n",
    "            self.parent[root_x] = root_y\n",
    "            self.size[root_y] += self.size[root_x]\n",
    "\n",
    "        # self.parent[root_x] = root_y\n",
    "        self.count -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "        for edge in edges:\n",
    "            self.union(edge[0], edge[1])\n",
    "        return self.count\n",
    "    \n",
    "    def find(self, x):\n",
    "        while self.parent[x] != x:\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        \n",
    "        self.parent[root_x] = root_y\n",
    "        self.count -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "\n",
    "        for edge in edges:\n",
    "            self.union(edge[0], edge[1])\n",
    "        return self.count\n",
    "    \n",
    "    def find(self, x):\n",
    "        while self.parent[x] != x:\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        self.parent[root_x] = root_y\n",
    "        self.count -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        AL = [[] for _ in range(n)]\n",
    "        for e in edges:\n",
    "            AL[e[0]].append(e[1])\n",
    "            AL[e[1]].append(e[0])\n",
    "        vis = [ False for _ in range(n)]\n",
    "        cc = 0\n",
    "        for v in range(n):\n",
    "            if not vis[v]:\n",
    "                cc += 1\n",
    "                # DFS\n",
    "                stack = [v]\n",
    "                while stack:\n",
    "                    v = stack.pop()\n",
    "                    vis[v] = True                  \n",
    "                    stack.extend([ i for i in AL[v][::-1] if not vis[i]] )\n",
    "        return cc\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        adj = collections.defaultdict(list)\n",
    "        for v1, v2 in edges:\n",
    "            adj[v1].append(v2)\n",
    "            adj[v2].append(v1)\n",
    "\n",
    "        count = n - len(adj)\n",
    "        while adj:\n",
    "            _, vlist = adj.popitem()\n",
    "            while vlist:\n",
    "                v = vlist.pop()\n",
    "                if v in adj:\n",
    "                    vlist.extend(adj.pop(v))\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uoionset = UnionSet(n)\n",
    "        # print(uoionset.father)\n",
    "        for u,v in edges:\n",
    "            uoionset.union(u,v)\n",
    "        \n",
    "        return len(set(uoionset.find(x) for x in range(n)))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self,n):\n",
    "        self.father = [i for i in range(n)]\n",
    "        self.rank = [0] * n \n",
    "\n",
    "    def find(self,x):\n",
    "        while x != self.father[x]:\n",
    "            x = self.father[x]\n",
    "        return x \n",
    "\n",
    "    def union(self,x,y):\n",
    "        x_root = self.find(x)\n",
    "        y_root = self.find(y)\n",
    "\n",
    "        if x_root != y_root:\n",
    "            if self.rank[x_root] > self.rank[y_root]:\n",
    "                self.father[y_root] = x_root\n",
    "            elif self.rank[x_root] < self.rank[y_root]:\n",
    "                self.father[x_root] = y_root\n",
    "            else:\n",
    "                self.father[x_root] = y_root\n",
    "                self.rank[y_root] += 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        m = collections.defaultdict(list)\n",
    "\n",
    "        for a, b in edges:\n",
    "            m[a].append(b)\n",
    "            m[b].append(a)\n",
    "\n",
    "        count = n - len(m)\n",
    "        while m:\n",
    "            for k in m:\n",
    "                todo = [k]\n",
    "                break\n",
    "            while todo:\n",
    "                tmp = []\n",
    "                for k in todo:\n",
    "                    tmp.extend(m[k])\n",
    "                    m.pop(k)\n",
    "                todo = tmp\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.part = n\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for _ in range(n)]\n",
    "\n",
    "    def Find(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        return self.Find(self.parent[x])\n",
    "\n",
    "    def Union(self, x: int, y: int) -> bool:\n",
    "        root_x = self.Find(x)\n",
    "        root_y = self.Find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "    \n",
    "    def in_the_same_part(self, x: int, y: int) -> bool:\n",
    "        return self.Find(x) == self.Find(y)\n",
    "    \n",
    "    def get_part_size(self, x: int) -> int:\n",
    "        root_x = self.Find(x)\n",
    "        return self.size[root_x]\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        UF = UnionFind(n)\n",
    "        for x, y in edges:\n",
    "            UF.Union(x, y)\n",
    "        return UF.part\n",
    "\"\"\"\n",
    "作者：HanXin\n",
    "链接：https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/solutions/631771/c-python3-bing-cha-ji-bu-jiu-shi-wei-lia-i6fl/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections \n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "\n",
    "        visited = [False] * n\n",
    "\n",
    "        def bfs(node):\n",
    "            queue = collections.deque([])\n",
    "            queue.append(node)\n",
    "            visited[node] = True \n",
    "\n",
    "            while queue:\n",
    "                cur_node = queue.popleft()\n",
    "                for nbr in graph[cur_node]:\n",
    "                    if not visited[nbr]:\n",
    "                        queue.append(nbr)\n",
    "                        visited[nbr] = True\n",
    "\n",
    "        res = 0 \n",
    "        for node in range(n):\n",
    "            if not visited[node]:\n",
    "                res += 1 \n",
    "                bfs(node)\n",
    "        \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet(object):\n",
    "    def __init__(self, data_list):\n",
    "        # initialize two dicts, one save the fathers of the nodes,\n",
    "        # the other save the size of the father node \n",
    "        # when initialization, the father of each node is itself \n",
    "        # all the sizes are set to be 1\n",
    "\n",
    "        self.father_dict = {}\n",
    "        self.size_dict = {}\n",
    "\n",
    "        for node in data_list:\n",
    "            self.father_dict[node] = node\n",
    "            self.size_dict[node] = 1\n",
    "\n",
    "    def find(self, node):\n",
    "        # use recursive way to search the root of the node \n",
    "        # when searching, put the node directly points to its root to let the tree shorter\n",
    "\n",
    "        father = self.father_dict[node]\n",
    "        if(node != father):\n",
    "            if father != self.father_dict[father]:    \n",
    "                # when optimize the tree, make sure the size of the father dict is corrcet \n",
    "                self.size_dict[father] -= 1\n",
    "            father = self.find(father)\n",
    "        self.father_dict[node] = father\n",
    "        return father\n",
    "\n",
    "    def is_same_set(self, node_a, node_b):\n",
    "        # set whether two nodes are in the same set, check whether the roots are the same\n",
    "        return self.find(node_a) == self.find(node_b)\n",
    "\n",
    "    def union(self, node_a, node_b):\n",
    "        # combine two sets \n",
    "        if node_a is None or node_b is None:\n",
    "            return\n",
    "\n",
    "        a_head = self.find(node_a)\n",
    "        b_head = self.find(node_b)\n",
    "\n",
    "        if(a_head != b_head):\n",
    "            a_set_size = self.size_dict[a_head]\n",
    "            b_set_size = self.size_dict[b_head]\n",
    "            if(a_set_size >= b_set_size):\n",
    "                self.father_dict[b_head] = a_head\n",
    "                self.size_dict[a_head] = a_set_size + b_set_size\n",
    "            else:\n",
    "                self.father_dict[a_head] = b_head\n",
    "                self.size_dict[b_head] = a_set_size + b_set_size\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        UFS = UnionFindSet(list(range(n)))\n",
    "        \n",
    "        res = n \n",
    "        for edge in edges:\n",
    "            if not UFS.is_same_set(edge[0], edge[1]):\n",
    "                UFS.union(edge[0], edge[1])\n",
    "                res -= 1 \n",
    "\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        adj = collections.defaultdict(list)\n",
    "        for v1, v2 in edges:\n",
    "            adj[v1].append(v2)\n",
    "            adj[v2].append(v1)\n",
    "\n",
    "        count = n - len(adj)\n",
    "        while adj:\n",
    "            for v in adj:\n",
    "                vlist = [v]\n",
    "                break\n",
    "            while vlist:\n",
    "                tmp = []\n",
    "                for v in vlist:\n",
    "                    if v in adj:\n",
    "                        tmp.extend(adj[v])\n",
    "                        del adj[v]\n",
    "                vlist = tmp\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        图的遍历有 dfs/bfs 和并查集两种写法， 这题挺有示范意义的\n",
    "        \"\"\"\n",
    "        adj = collections.defaultdict(list)\n",
    "        for v1, v2 in edges:\n",
    "            adj[v1].append(v2)\n",
    "            adj[v2].append(v1)\n",
    "\n",
    "        count = n - len(adj)\n",
    "        # dfs\n",
    "        while adj:\n",
    "            _, vlist = adj.popitem()\n",
    "            while vlist:\n",
    "                v = vlist.pop()\n",
    "                if v in adj:\n",
    "                    vlist.extend(adj.pop(v))\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        #BFS\n",
    "        dic=defaultdict(list)\n",
    "        visited=set()\n",
    "        queue=[]\n",
    "        cnt=0\n",
    "        for edge in edges:\n",
    "            dic[edge[0]].append(edge[1])\n",
    "            dic[edge[1]].append(edge[0])\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                visited.add(i)\n",
    "                cnt+=1\n",
    "                queue.append(i)\n",
    "                while queue:\n",
    "                    cur=queue.pop()\n",
    "                    for v in dic[cur]:\n",
    "                        if v not in visited:\n",
    "                            visited.add(v)\n",
    "                            queue.append(v)\n",
    "        return cnt \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        class Node:\n",
    "            def __init__(self):\n",
    "                self.father=self\n",
    "        dic={}\n",
    "        for i in range(n):\n",
    "            dic[i]=Node()\n",
    "\n",
    "        def method(node):\n",
    "            if node.father==node:\n",
    "                return node\n",
    "            else:\n",
    "                return method(node.father)\n",
    "\n",
    "        for line in edges:\n",
    "            node_1=dic[line[0]]\n",
    "            node_2=dic[line[1]]\n",
    "\n",
    "            father_1=method(node_1)\n",
    "            father_2=method(node_2)\n",
    "\n",
    "            if father_1!=father_2:\n",
    "                father_2.father=father_1\n",
    "\n",
    "            \n",
    "        result=set([])\n",
    "        for i in range(n):\n",
    "            result.add(method(dic[i]))\n",
    "        return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = {}\n",
    "        for start, end in edges:\n",
    "            if start in graph:\n",
    "                graph[start].append(end)\n",
    "            else:\n",
    "                graph[start] = [end]\n",
    "\n",
    "            if end in graph:\n",
    "                graph[end].append(start)\n",
    "            else:\n",
    "                graph[end] = [start]\n",
    "\n",
    "        connected = []\n",
    "        for i in range(n):\n",
    "            if all([i not in x for x in connected]):\n",
    "                connected.append(self.getGraph(graph, i))\n",
    "\n",
    "        return len(connected)\n",
    "\n",
    "\n",
    "    def getGraph(self, graph, start):\n",
    "        node = set([start])\n",
    "        s = []\n",
    "        if start in graph:\n",
    "            s = graph[start]\n",
    "        while len(s) > 0:\n",
    "            v = s.pop()\n",
    "            if v in graph and v not in node:\n",
    "                node.add(v)\n",
    "                s += graph[v]\n",
    "        \n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if dc[x] != x: dc[x] = find(dc[x])\n",
    "            return dc[x]\n",
    "        dc = [i for i in range(n)]\n",
    "        for i,j in edges:\n",
    "            dc[find(i)] = find(j)\n",
    "        return sum(dc[i]==i for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        parent = list(range(n))\n",
    "        def find_parent(i):\n",
    "            if parent[i] == i:\n",
    "                return i\n",
    "            parent[i] = find_parent(parent[i])\n",
    "            return parent[i]\n",
    "        \n",
    "        for edge in edges:\n",
    "            x = find_parent(edge[0])\n",
    "            y = find_parent(edge[1])\n",
    "            if x != y:\n",
    "                parent[x] = y\n",
    "        print(parent)\n",
    "        return sum([1 for i, p in enumerate(parent) if p == i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        edges.sort()\n",
    "        graphs = []\n",
    "        for edge in edges:\n",
    "            flag1 = flag2 = -1\n",
    "            for gi, g in enumerate(graphs):\n",
    "                if flag1==-1:\n",
    "                    if edge[0] in g:\n",
    "                        flag1 = gi\n",
    "                if flag2==-1:\n",
    "                    if edge[1] in g:\n",
    "                        flag2 = gi\n",
    "                if flag1!=-1 and flag2!=-1:\n",
    "                    break\n",
    "            else:\n",
    "                if flag1==flag2==-1:\n",
    "                    graphs.append(set())\n",
    "                    flag1 = flag2 = len(graphs)-1\n",
    "            if flag1!=-1:\n",
    "                graphs[flag1].add(edge[0])\n",
    "                graphs[flag1].add(edge[1])\n",
    "            if flag2!=-1:\n",
    "                graphs[flag2].add(edge[0])\n",
    "                graphs[flag2].add(edge[1])\n",
    "            if flag1 != flag2 and flag1!=-1 and flag2!=-1:\n",
    "                graphs[flag1] = graphs[flag1]|graphs[flag2]\n",
    "                graphs = graphs[:flag2]+graphs[flag2+1:]\n",
    "        link = len(graphs)\n",
    "        print(graphs)\n",
    "        for i in range(n):\n",
    "            flag = False\n",
    "            for g in graphs:\n",
    "                if i in g:\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                link += 1\n",
    "        return link"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        if len(edges) == 0:\n",
    "            return n\n",
    "\n",
    "        \n",
    "        def fen(edg: list):\n",
    "            if len(edg) == 1:\n",
    "                return edg\n",
    "            mid = len(edg) // 2\n",
    "            left = fen(edg[:mid])\n",
    "            right = fen(edg[mid:])\n",
    "            return he(left, right)\n",
    "\n",
    "\n",
    "        def he(l: list, r: list):\n",
    "            li = []\n",
    "            for i in l:\n",
    "                f = 0\n",
    "                ll = list(set(i))\n",
    "                for j in range(len(r)):\n",
    "                    for k in ll:\n",
    "                        if k in r[j]:\n",
    "                            r[j].extend(ll)\n",
    "                            f = 1\n",
    "                            break\n",
    "                    if f:\n",
    "                        break\n",
    "                if not f:\n",
    "                    li.append(i)\n",
    "            r.extend(li)\n",
    "            return r\n",
    "\n",
    "\n",
    "        v_list = fen(fen(fen(fen(fen(edges)))))\n",
    "        for i in range(10):\n",
    "            v_list = fen(v_list)\n",
    "        v_list2 = []\n",
    "        if len(v_list) == 2:\n",
    "            sl = list(set(v_list[0]))\n",
    "            for i in sl:\n",
    "                if i in v_list[1]:\n",
    "                    sl.extend(v_list[1])\n",
    "                    v_list2.append(sl)\n",
    "                    break\n",
    "        if len(v_list2) > 0:\n",
    "            n -= len(set(v_list2[0]))\n",
    "            return (n + len(v_list2))\n",
    "        else:\n",
    "            for i in v_list:\n",
    "                n -= len(set(i))\n",
    "            return (n + len(v_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        p = dict()\n",
    "        def find(i):\n",
    "            if i not in p:\n",
    "                p[i] = i\n",
    "                return i\n",
    "            if p[i] == i:\n",
    "                return i\n",
    "                \n",
    "            pi = find(p[i])\n",
    "            p[i] = pi\n",
    "            return pi\n",
    "        \n",
    "        def union(i, j):\n",
    "            pi, pj = find(i), find(j)\n",
    "            p[pi] = pj\n",
    "            find(i)\n",
    "            \n",
    "        for i, j in edges:\n",
    "            union(i,j)\n",
    "        \n",
    "        \n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            s.add(find(i))\n",
    "            \n",
    "        return len(s)\n",
    "            \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "求联通块的个数，需要遍历所有的节点\n",
    "\n",
    "给定n个节点，标记为0到n-1，并给定一无向图的边列表（每一边是一对节点),找出多少个component\n",
    "\n",
    "把所有节点都遍历一遍，如果没有访问过，说明是新的起点\n",
    "增加一个联通块数量\n",
    "在新的起点上做bfs,找到一个联通块\n",
    "\"\"\"\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        res = 0\n",
    "        visited = set()\n",
    "\n",
    "        for node in range(n):\n",
    "            if node not in visited:\n",
    "                res += 1\n",
    "                queue = deque([(node, -1)])\n",
    "                \n",
    "                while queue:\n",
    "                    cur_node, parent = queue.popleft()\n",
    "\n",
    "                    if cur_node in visited:\n",
    "                        continue\n",
    "\n",
    "                    visited.add(cur_node)\n",
    "                    for neighbor in graph[cur_node]:\n",
    "                        if neighbor == parent:\n",
    "                            continue\n",
    "                        queue.append((neighbor, cur_node))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        part = n\n",
    "        parent = [i for i in range(n)]\n",
    "        size = [1 for _ in range(n)]\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        # def union(x, y):\n",
    "        #     rx = find(x)\n",
    "        #     ry = find(y)\n",
    "        #     if rx == ry:\n",
    "        #         return \n",
    "        #     else:\n",
    "        #         parent[rx] = ry\n",
    "        #         size[ry] += size[rx]\n",
    "        #         return\n",
    "        for x, y in edges:\n",
    "            rx = find(x)\n",
    "            ry = find(y)\n",
    "            if rx != ry:\n",
    "                parent[rx] = ry\n",
    "                part -= 1\n",
    "        return part"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        part = n\n",
    "        parent = [i for i in range(n)]\n",
    "        # size = [1 for _ in range(n)]\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        for x, y in edges:\n",
    "            rx = find(x)\n",
    "            ry = find(y)\n",
    "            if rx != ry:\n",
    "                parent[rx] = ry\n",
    "                part -= 1\n",
    "        return part"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        if len(edges) == 0:\n",
    "            return n\n",
    "\n",
    "        \n",
    "        def fen(edg: list):\n",
    "            if len(edg) == 1:\n",
    "                return edg\n",
    "            mid = len(edg) // 2\n",
    "            left = fen(edg[:mid])\n",
    "            right = fen(edg[mid:])\n",
    "            return he(left, right)\n",
    "\n",
    "\n",
    "        def he(l: list, r: list):\n",
    "            li = []\n",
    "            for i in l:\n",
    "                f = 0\n",
    "                ll = list(set(i))\n",
    "                for j in range(len(r)):\n",
    "                    for k in ll:\n",
    "                        if k in r[j]:\n",
    "                            r[j].extend(ll)\n",
    "                            f = 1\n",
    "                            break\n",
    "                    if f:\n",
    "                        break\n",
    "                if not f:\n",
    "                    li.append(i)\n",
    "            r.extend(li)\n",
    "            return r\n",
    "\n",
    "\n",
    "        v_list = fen(edges)\n",
    "        len1 = len(v_list)\n",
    "        while 1:\n",
    "            v_list = fen(v_list)\n",
    "            if len1 == len(v_list):\n",
    "                break\n",
    "            len1 = len(v_list)\n",
    "        v_list2 = []\n",
    "        if len(v_list) == 2:\n",
    "            sl = list(set(v_list[0]))\n",
    "            for i in sl:\n",
    "                if i in v_list[1]:\n",
    "                    sl.extend(v_list[1])\n",
    "                    v_list2.append(sl)\n",
    "                    break\n",
    "        if len(v_list2) > 0:\n",
    "            n -= len(set(v_list2[0]))\n",
    "            return (n + len(v_list2))\n",
    "        else:\n",
    "            for i in v_list:\n",
    "                n -= len(set(i))\n",
    "            return (n + len(v_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        def devide(node_set):\n",
    "            if len(node_set) == 0:\n",
    "                return \n",
    "            temp_node_list = [list(node_set)[0]]\n",
    "            while(temp_node_list):\n",
    "                temp_node = temp_node_list[0]\n",
    "                del temp_node_list[0]\n",
    "                for node in record[temp_node]:\n",
    "                    if node in node_set:\n",
    "                        temp_node_list.append(node)\n",
    "                        node_set.remove(node)\n",
    "                        \n",
    "            self.cp += 1\n",
    "            devide(node_set)\n",
    "\n",
    "        self.cp = 0\n",
    "        record = collections.defaultdict(list)\n",
    "        node_set = set()\n",
    "        for edge in edges:\n",
    "            record[edge[0]].append(edge[1])\n",
    "            record[edge[1]].append(edge[0])\n",
    "            for node in edge:\n",
    "                node_set.add(node)\n",
    "        self.alone_node = n - len(node_set)\n",
    "        devide(node_set)\n",
    "        return self.cp + self.alone_node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        edge_dict = defaultdict(set)\n",
    "\n",
    "        for a, b in edges:\n",
    "            edge_dict[a].add(b)\n",
    "            edge_dict[b].add(a)\n",
    "        \n",
    "        nodes = set([node for node in range(n)])\n",
    "\n",
    "        cnt = 0\n",
    "        while nodes:\n",
    "            cnt += 1\n",
    "            bfs = set([list(nodes)[0]])\n",
    "            while bfs:\n",
    "                next_bfs = set()\n",
    "                for n in bfs:\n",
    "                    for nn in edge_dict[n]:\n",
    "                        next_bfs.add(nn)\n",
    "                        edge_dict[nn].remove(n)\n",
    "                    del(edge_dict[n])\n",
    "                    if n in nodes:\n",
    "                        nodes.remove(n)\n",
    "                bfs = next_bfs\n",
    "        \n",
    "        return cnt\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class UnionFind(object):\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.part = n\n",
    "    \n",
    "    def union(self, node1, node2):\n",
    "        if self.find(node1, node2):\n",
    "            return\n",
    "        r1 = self.root(node1)\n",
    "        r2 = self.root(node2)\n",
    "        self.parent[r1] = r2\n",
    "        self.part -= 1\n",
    "\n",
    "\n",
    "    def find(self, node1, node2):\n",
    "        r1, r2 = self.root(node1), self.root(node2)\n",
    "        return r1 == r2\n",
    "    \n",
    "    def root(self, node):\n",
    "        def dp(node):\n",
    "            if self.parent[node] == node:\n",
    "                return node\n",
    "            return dp(self.parent[node])\n",
    "        return dp(node)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        for a, b in edges:\n",
    "            uf.union(a, b)\n",
    "        return uf.part\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 记录访问过的节点\n",
    "        visited = defaultdict(int)\n",
    "        ans = 0\n",
    "        # 创建领接表\n",
    "        ll = defaultdict(list)\n",
    "        for i,j in edges:\n",
    "            ll[i].append(j)\n",
    "            ll[j].append(i)\n",
    "        def dfs(i):\n",
    "            # 深度遍历\n",
    "            # 如果节点已经访问，返回\n",
    "            if visited[i]:\n",
    "                return\n",
    "            visited[i] = 1\n",
    "            for d in ll[i]:\n",
    "                dfs(d)\n",
    "        def bfs(i):\n",
    "            # 此处的i一定没有访问过\n",
    "            temp = [i]\n",
    "            while temp:\n",
    "                d = temp.pop()\n",
    "                if not visited[d]:\n",
    "                    visited[d] = 1\n",
    "                    for dd in ll[d]:\n",
    "                        temp.append(dd)\n",
    "            \n",
    "        \n",
    "        \n",
    "        for num in range(n):\n",
    "            if not visited[num]:\n",
    "                bfs(num)\n",
    "                #dfs(num)\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.cnt = n\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "    def find(self, x):\n",
    "        if self.root[x] == x:\n",
    "            return x\n",
    "        return self.find(self.root[x])\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        if self.size[x] > self.size[y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y # 一开始写成self.root[x] = root_y，部分通过\n",
    "        self.size[root_y] += self.size[root_x] # 不能写成self.size[y] += self.size[x]\n",
    "        self.cnt -= 1\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        UF = UnionFind(n)\n",
    "        for i in edges:\n",
    "            UF.union(i[0], i[1])\n",
    "        return UF.cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        connects=dict()\n",
    "        for i in range(n):\n",
    "            connects[i]=set()\n",
    "        for edge in edges:\n",
    "            connects[edge[0]].add(edge[1])\n",
    "            connects[edge[1]].add(edge[0])\n",
    "        not_visited={i for i in range(n)}\n",
    "        \n",
    "        comp=0\n",
    "        while not_visited:\n",
    "            comp+=1\n",
    "            this_node=min(list(not_visited))\n",
    "            queue=[this_node]\n",
    "            not_visited.remove(this_node)\n",
    "            while queue:\n",
    "                head=queue.pop(0)\n",
    "                for node in connects[head]:\n",
    "                    if node in not_visited:\n",
    "                        not_visited.remove(node)\n",
    "                        queue.append(node)\n",
    "        return comp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        vis = [0 for i in range(n)]\n",
    "\n",
    "        graph = [[] for _ in range(n)]\n",
    "\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        \n",
    "        def dfs(i):\n",
    "            if vis[i] == 1:\n",
    "                return\n",
    "            \n",
    "            vis[i] = 1\n",
    "            for j in graph[i]:\n",
    "                dfs(j)\n",
    "        \n",
    "        ct = 0\n",
    "        for i in range(n):\n",
    "            if vis[i] == 0:\n",
    "                ct += 1\n",
    "                dfs(i)\n",
    "        \n",
    "        return ct\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        parent = defaultdict(int)\n",
    "        son = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            parent[i] = i\n",
    "            son[i] = [i]\n",
    "        ans = n\n",
    "        for e in edges:\n",
    "            # e.sort()\n",
    "            if not parent[e[0]]==parent[e[1]]:\n",
    "                ans -= 1\n",
    "                son[parent[e[0]]].extend(son[parent[e[1]]])\n",
    "                for k in son[parent[e[1]]]:\n",
    "                    parent[k] = parent[e[0]]\n",
    "        return ans\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        edge_map = collections.defaultdict(list)\n",
    "        for i,j in edges:\n",
    "            edge_map[i].append(j)\n",
    "            edge_map[j].append(i)\n",
    "        visited = [False]*n\n",
    "        res = 0\n",
    "        def DFS(point):\n",
    "            if visited[point] == True:\n",
    "                return\n",
    "            visited[point] = True\n",
    "            for node in edge_map[point]:\n",
    "                DFS(node)\n",
    "    \n",
    "        for i in range(n):\n",
    "            if visited[i] != True:\n",
    "                DFS(i)\n",
    "                res += 1\n",
    "            elif visited[i] == True:\n",
    "                continue\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            adj[edge[0]].append(edge[1])\n",
    "            adj[edge[1]].append(edge[0])\n",
    "        \n",
    "        vis = [False] * n\n",
    "\n",
    "        def dfs(k):\n",
    "            vis[k] = True\n",
    "            for m in adj[k]:\n",
    "                if not vis[m]:\n",
    "                    dfs(m)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                dfs(i)\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        visited = defaultdict(int)\n",
    "        ans = 0\n",
    "        # 创建领接表\n",
    "        ll = defaultdict(list)\n",
    "        for i,j in edges:\n",
    "            ll[i].append(j)\n",
    "            ll[j].append(i)\n",
    "        def dfs(i):\n",
    "            # 深度遍历\n",
    "            # 如果节点已经访问，返回\n",
    "            if visited[i]:\n",
    "                return\n",
    "            visited[i] = 1\n",
    "            for d in ll[i]:\n",
    "                dfs(d)\n",
    "        def bfs(i):\n",
    "            # 此处的i一定没有访问过\n",
    "            temp = [i]\n",
    "            while temp:\n",
    "                d = temp.pop()\n",
    "                if not visited[d]:\n",
    "                    visited[d] = 1\n",
    "                    for dd in ll[d]:\n",
    "                        temp.append(dd)\n",
    "            \n",
    "        \n",
    "        \n",
    "        for num in range(n):\n",
    "            if not visited[num]:\n",
    "                bfs(num)\n",
    "                #dfs(num)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        v = [False]*n\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        def dfs(i):\n",
    "            v[i] = True\n",
    "            for j in g[i]:\n",
    "                if not v[j]:\n",
    "                    dfs(j)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if not v[i]:\n",
    "                dfs(i)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        v = [False]*n\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        def dfs(i):\n",
    "            v[i] = True\n",
    "            for j in g[i]:\n",
    "                if not v[j]:\n",
    "                    dfs(j)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if not v[i]:\n",
    "                dfs(i)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        pre_to_post = [[] for _ in range(n)]\n",
    "\n",
    "        for edge in edges:\n",
    "            pre_to_post[edge[0]].append(edge[1])\n",
    "            pre_to_post[edge[1]].append(edge[0])\n",
    "\n",
    "        self.visited = [0 for _ in range(n)]\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        def DFS(i):\n",
    "            if self.visited[i] == 1:\n",
    "                return\n",
    "            self.visited[i] = 1\n",
    "            for post in pre_to_post[i]:\n",
    "                DFS(post)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if self.visited[i] == 0:\n",
    "                ret += 1\n",
    "                DFS(i)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        import collections\n",
    "        connected_node_map = collections.defaultdict(list)\n",
    "        for pair in edges:\n",
    "            connected_node_map[pair[0]].append(pair[1])\n",
    "            connected_node_map[pair[1]].append(pair[0])\n",
    "        visited = {}\n",
    "        def dfs(node_no):\n",
    "            if node_no not in visited:\n",
    "                visited[node_no] = True\n",
    "                try:\n",
    "                    for next_node in connected_node_map[node_no]:\n",
    "                        dfs(next_node)\n",
    "                except:\n",
    "                    pass\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        v = [False]*n\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        def dfs(i):\n",
    "            v[i] = True\n",
    "            for j in g[i]:\n",
    "                if not v[j]:\n",
    "                    dfs(j)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if not v[i]:\n",
    "                dfs(i)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        map = defaultdict(list)\n",
    "\n",
    "        for n1, n2 in edges:\n",
    "            map[n1].append(n2)\n",
    "            map[n2].append(n1)\n",
    "\n",
    "        visited = set()\n",
    "\n",
    "        def DFS(node):\n",
    "            if node in visited:\n",
    "                return\n",
    "\n",
    "            visited.add(node)\n",
    "\n",
    "            for neigh_node in map[node]:\n",
    "                DFS(neigh_node)\n",
    "\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        for node in map:\n",
    "            if node not in visited:\n",
    "                DFS(node)\n",
    "                res += 1\n",
    "\n",
    "        return res + n - len(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = {}\n",
    "        go = []\n",
    "        for i in range(n):\n",
    "            graph[i] = []\n",
    "            go.append(0)\n",
    "        for i in range(len(edges)):\n",
    "            e1, e2 = edges[i]\n",
    "            graph[e1].append(e2)\n",
    "            graph[e2].append(e1)\n",
    "\n",
    "        def dfs(n, i):\n",
    "            go[i] = 1\n",
    "            for j in graph[i]:\n",
    "                if go[j] == 0:\n",
    "                    dfs(n, j)\n",
    "\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            if go[i] == 0:\n",
    "                dfs(n, i)\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        v=[False]*n\n",
    "        g=collections.defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        def dfs(i):\n",
    "            v[i]=True\n",
    "            for j in g[i]:\n",
    "                if v[j]==False:\n",
    "                    dfs(j)\n",
    "        \n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if v[i]==False:\n",
    "                dfs(i)\n",
    "                ans+=1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        vis = set()\n",
    "        def dfs(i):\n",
    "            for j in g[i]:\n",
    "                if j not in vis:\n",
    "                    vis.add(j)\n",
    "                    dfs(j)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i not in vis:\n",
    "                res += 1\n",
    "                dfs(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import defaultdict\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        visited = set()\n",
    "        count = 0\n",
    "\n",
    "        neighbors = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            neighbors[x].append(y)\n",
    "            neighbors[y].append(x)\n",
    "\n",
    "        def dfs(node):\n",
    "            visited.add(node)\n",
    "            for neighbor in neighbors[node]:\n",
    "                if neighbor not in visited:\n",
    "                    dfs(neighbor)\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        def dfs(u):\n",
    "            for node in graph[u]:\n",
    "                if node not in visited:\n",
    "                    visited.add(node)\n",
    "                    dfs(node)\n",
    "\n",
    "        count = 0\n",
    "        edges.sort()\n",
    "        visited = set()\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                count += 1\n",
    "                dfs(i)\n",
    "        return count\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        visited = set()\n",
    "        dic = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            dic[a].append(b)\n",
    "            dic[b].append(a)\n",
    "        def dfs(cur):\n",
    "            if cur in visited:\n",
    "                return\n",
    "            visited.add(cur)\n",
    "            neis = dic[cur]\n",
    "            for nei in neis:\n",
    "                dfs(nei)\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                res += 1\n",
    "                dfs(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        visited = set()\n",
    "\n",
    "        dic = defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            dic[i].append(j)\n",
    "            dic[j].append(i)\n",
    "\n",
    "        def dfs(cur):\n",
    "            if cur in visited:\n",
    "                return\n",
    "            visited.add(cur)\n",
    "            for nei in dic[cur]:\n",
    "                dfs(nei)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.count = n\n",
    "\n",
    "    def union(self, a, b):\n",
    "        rootA = self.find(a)\n",
    "        rootB = self.find(b)\n",
    "\n",
    "        if rootA == rootB:\n",
    "            return\n",
    "\n",
    "        self.parent[rootA] = rootB\n",
    "        self.count -= 1\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def get_count(self):\n",
    "        return self.count\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UF(n)\n",
    "\n",
    "        for a, b in edges:\n",
    "            uf.union(a, b)\n",
    "\n",
    "        return uf.get_count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.f = {}\n",
    "    \n",
    "    def findParent(self, x):\n",
    "        y = self.f.get(x,x)\n",
    "        if x!=y:\n",
    "            y = self.f[x] = self.findParent(y)\n",
    "        return y\n",
    "\n",
    "    def union(self, x, y):\n",
    "        self.f[self.findParent(x)] = self.findParent(y)\n",
    "    \n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dsu = UnionFind()\n",
    "        for a,b in edges:\n",
    "            dsu.union(a, b)\n",
    "        return len(set(dsu.findParent(x) for x in range(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        father = [i for i in range(n)]\n",
    "        for i, j in edges:\n",
    "            self.union(father, i, j)\n",
    "        rootset = set()\n",
    "        for i in range(n):\n",
    "            rootset.add(self.find(father, i))\n",
    "        return len(rootset)\n",
    "        \n",
    "    def find(self, father, i):\n",
    "        if father[i] != i:\n",
    "            father[i] = self.find(father, father[i])\n",
    "        return father[i]\n",
    "\n",
    "    def union(self, father, i, j):\n",
    "        i_root, j_root = self.find(father, i), self.find(father, j)\n",
    "        if i_root == j_root:\n",
    "            return \n",
    "        father[i_root] = j_root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "\n",
    "        for edge in edges:\n",
    "            self.union(edge[0], edge[1])\n",
    "        return self.count\n",
    "    \n",
    "    def find(self, x):\n",
    "        while self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        self.parent[root_x] = root_y\n",
    "        self.count -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.count = n\n",
    "        for edge in edges:\n",
    "            self.union(edge[0], edge[1])\n",
    "\n",
    "        return self.count\n",
    "\n",
    "    def union(self, a, b):\n",
    "        root_a = self.find(a)\n",
    "        root_b = self.find(b)\n",
    "        if root_a == root_b:\n",
    "            return \n",
    "        self.parent[root_a] = root_b \n",
    "        self.count -= 1 \n",
    "        \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "\n",
    "        for edge in edges:\n",
    "            self.union(edge[0], edge[1])\n",
    "        return self.count\n",
    "    \n",
    "    def find(self, x):\n",
    "        while self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        self.parent[root_x] = root_y\n",
    "        self.count -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self,n):\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "\n",
    "    def find(self, p):\n",
    "        if self.parent[p]!= p:\n",
    "            self.parent[p] = self.find(self.parent[p])\n",
    "        return self.parent[p]\n",
    "\n",
    "    def union(self,p,q):\n",
    "        rootp = self.find(p)\n",
    "        rootq = self.find(q)\n",
    "\n",
    "        if rootp == rootq:\n",
    "            return\n",
    "        \n",
    "        self.parent[rootp] = rootq\n",
    "        self.count -= 1\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UF(n)\n",
    "        for x,y in edges:\n",
    "            uf.union(x, y)\n",
    "        return uf.count\n",
    "\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.parents = []\n",
    "        self.count = None\n",
    "\n",
    "    def union(self, p, q):\n",
    "        root_p = self.find(p)\n",
    "        root_q = self.find(q)\n",
    "        if root_p == root_q:\n",
    "            return\n",
    "        self.parents[root_p] = root_q\n",
    "        self.count -= 1\n",
    "    \n",
    "    def find(self, p):\n",
    "        while p != self.parents[p]:\n",
    "            p = self.find(self.parents[p])\n",
    "        return p\n",
    "        \n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        self.parents = [i for i in range(n)]\n",
    "        self.count = n\n",
    "\n",
    "        for edge in edges:\n",
    "            self.union(edge[0], edge[1])\n",
    "        \n",
    "        return self.count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        parents = [x for x in range(n+1)]\n",
    "\n",
    "        def find(x):\n",
    "            px = parents[x]\n",
    "            if px != x:\n",
    "                px = find(px)\n",
    "            return px\n",
    "\n",
    "        def union(x, y):\n",
    "            px, py = find(x), find(y)\n",
    "            if px != py:\n",
    "                parents[px] = y\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        for a, b in edges:\n",
    "            if not union(a, b):\n",
    "                n -= 1\n",
    "        \n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        myuni = unifind(n)\n",
    "        for edg in edges:\n",
    "            myuni.connect(edg[0],edg[1])\n",
    "        return myuni.count\n",
    "\n",
    "\n",
    "class unifind:\n",
    "    def __init__(self,number):\n",
    "        self.parent = [i for i in range(number)] \n",
    "        self.count = number \n",
    "        # for \n",
    "    def find(self,number):\n",
    "        px = self.parent[number]\n",
    "        if px!=number:\n",
    "            self.parent[number] = self.find(self.parent[number])\n",
    "        return self.parent[number]\n",
    "    def connect(self,num1,num2):\n",
    "        root1 = self.find(num1)\n",
    "        root2 = self.find(num2)\n",
    "        if root1==root2:\n",
    "            return \n",
    "        self.parent[root1] = root2 \n",
    "        self.count-=1 \n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self):\n",
    "        self.parents = dict()\n",
    "        self.cnt = 0\n",
    "\n",
    "    def find(self, u):\n",
    "        if u not in self.parents:\n",
    "            self.parents[u] = u\n",
    "            self.cnt += 1\n",
    "            return self.parents[u]\n",
    "        if u != self.parents[u]:\n",
    "            self.parents[u] = self.find(self.parents[u])\n",
    "        return self.parents[u]\n",
    "    \n",
    "    def union(self, u, v):\n",
    "        parent_u = self.find(u)\n",
    "        parent_v = self.find(v)\n",
    "        if parent_u == parent_v:\n",
    "            return\n",
    "        self.parents[parent_u] = parent_v\n",
    "        self.cnt -= 1\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UF()\n",
    "        for i in range(n):\n",
    "            uf.find(i)\n",
    "        for src, dest in edges:\n",
    "            uf.union(src, dest)\n",
    "        return uf.cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        parent = [i for i in range(n)]\n",
    "        global count\n",
    "        count = n\n",
    "        \n",
    "        def find_root(node):\n",
    "            root = parent[node]\n",
    "            if root == node:return node\n",
    "            return find_root(root)\n",
    "        \n",
    "        def union(a,b):\n",
    "            global count\n",
    "            root_a = find_root(a)\n",
    "            root_b = find_root(b)\n",
    "            if root_a != root_b:\n",
    "                parent[root_a] = root_b\n",
    "                count -= 1\n",
    "        \n",
    "\n",
    "        for edge in edges:\n",
    "            union(edge[0], edge[1])\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dict = {}\n",
    "        for i in range(n):\n",
    "            dict[i] = i\n",
    "        \n",
    "        def find(a: int) -> int:\n",
    "            p = dict[a]\n",
    "            if p == a:\n",
    "                return a\n",
    "            newP = find(p)\n",
    "            dict[a] = newP\n",
    "            return newP\n",
    "        count = 0\n",
    "        for e in edges:\n",
    "            p1 = find(e[0])\n",
    "            p2 = find(e[1])\n",
    "            if p1 != p2:\n",
    "                dict[p1] = p2\n",
    "                count+=1\n",
    "        return n-count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        fa=[i for i in range(n)]\n",
    "        c=n\n",
    "        def find(x):\n",
    "            if x!=fa[x]:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(a,b):\n",
    "            fa[find(a)]=find(b)\n",
    "        for a,b in edges:\n",
    "            if find(a)!=find(b):\n",
    "                c-=1\n",
    "                union(a,b)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        p = [i for i in range(n)]\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        for x, y in edges:\n",
    "            p[find(x)] = find(y)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += p[i] == i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # step1: 构建临接表\n",
    "        adjacency_list = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            u, v = edge\n",
    "            adjacency_list[u].append(v)\n",
    "            adjacency_list[v].append(u)\n",
    "        # step2: 初始化标记数组\n",
    "        visited = [False] * n\n",
    "        # step3: DFS遍历\n",
    "        def dfs(node):\n",
    "            visited[node] = True\n",
    "            for neighbor in adjacency_list[node]:\n",
    "                if not visited[neighbor]:\n",
    "                    dfs(neighbor)\n",
    "        # step4: 计数\n",
    "        connected_components = 0\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                dfs(i)\n",
    "                connected_components += 1\n",
    "        # step5: 返回结果\n",
    "        return connected_components"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = {}\n",
    "        for i,j in edges:\n",
    "            if i not in graph:\n",
    "                graph[i] = []\n",
    "            if j not in graph:\n",
    "                graph[j] = []\n",
    "            graph[i].append(j)\n",
    "            graph[j].append(i)\n",
    "    \n",
    "        def dfs(x):  \n",
    "            for con in graph[x]:\n",
    "                if con not in visited:\n",
    "                    visited.append(con)\n",
    "                    dfs(con)\n",
    "        visited = []\n",
    "        res = 0\n",
    "        for node in graph.keys():\n",
    "            if node in visited:\n",
    "                continue\n",
    "            \n",
    "            visited.append(node)\n",
    "            dfs(node)\n",
    "            res += 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                res += 1\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            graph[edge[1]].append(edge[0])\n",
    "            graph[edge[0]].append(edge[1])\n",
    "        #    print(graph)\n",
    "        # Initialize a set to keep track of visited nodes\n",
    "        visited = set()\n",
    "        # Count the number of connected components\n",
    "        count = 0\n",
    "        for node in range(n):\n",
    "            if node not in visited:\n",
    "                self.dfs(node, visited, graph)\n",
    "                count += 1\n",
    "        return count\n",
    "    def dfs(self, node, visited, graph):\n",
    "        visited.add(node)\n",
    "        for neighbor in graph[node]:\n",
    "            if neighbor not in visited:\n",
    "                self.dfs(neighbor, visited, graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        relations = [[] for _ in range(n)]\n",
    "        \n",
    "        \n",
    "        for edge in edges :\n",
    "            relations[edge[0]].append(edge[1])\n",
    "            relations[edge[1]].append(edge[0])\n",
    "        #print(relations)\n",
    "            \n",
    "        cnt = 0\n",
    "        visited = [0] *n #0 是未访问到\n",
    "        for i in range(n):\n",
    "            if visited[i] ==0 :\n",
    "                self.dfs( relations,i,visited)\n",
    "                cnt +=1\n",
    "        return cnt\n",
    "    def dfs(self,relations: List[List[int]],i: int,visited: List[int]):\n",
    "        visited[i] =1\n",
    "        #print(visited)\n",
    "        for k in relations[i]:\n",
    "            if visited[k] == 0:\n",
    "                self.dfs(relations,k,visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        visited = [False] * n\n",
    "        adj = {}\n",
    "        for i in range(n):\n",
    "            adj[i] = []\n",
    "        for i, j in edges:\n",
    "            adj[i].append(j)\n",
    "            adj[j].append(i)\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                self.dfs(adj, i, visited)\n",
    "                count += 1\n",
    "\n",
    "        return count\n",
    "    def dfs(self, adj, n, visited):\n",
    "        visited[n] = True\n",
    "        successers = adj[n]\n",
    "        for successer in successers:\n",
    "            if not visited[successer]:\n",
    "                self.dfs(adj, successer, visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        map = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            map[u].append(v)\n",
    "            map[v].append(u)\n",
    "        seen = set()\n",
    "        ans = 0\n",
    "\n",
    "\n",
    "        def dfs(u):\n",
    "            for v in map[u]:\n",
    "                if v not in seen:\n",
    "                    seen.add(v)\n",
    "                    dfs(v)\n",
    "                \n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in seen:\n",
    "                seen.add(i)\n",
    "                ans += 1\n",
    "                dfs(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dic = collections.defaultdict(list)\n",
    "        cnt = 0\n",
    "        isVisited = [0] * n\n",
    "\n",
    "        for a, b in edges:\n",
    "            dic[a].append(b)\n",
    "            dic[b].append(a)\n",
    "\n",
    "        def dfs(node):\n",
    "            if isVisited[node]:\n",
    "                return\n",
    "            isVisited[node] = 1\n",
    "            for n in dic[node]:\n",
    "                dfs(n)\n",
    "\n",
    "        for i in range(n):\n",
    "            if not isVisited[i]:\n",
    "                dfs(i)\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n",
    "\n",
    "        dic = collections.defaultdict(list)\n",
    "        cnt = 0\n",
    "        visited = [0] * n\n",
    "\n",
    "        # for a, b in edges:\n",
    "        #     dic[a].append(b)\n",
    "        #     dic[b].append(a)\n",
    "        \n",
    "\n",
    "        # def dfs(node):\n",
    "        #     if visited[node]: return\n",
    "        #     visited[node] = 1\n",
    "\n",
    "        #     for nei in dic[node]:\n",
    "        #         # if not visited[nei]:\n",
    "        #             dfs(nei)\n",
    "        \n",
    "        # for i in range(n):#range(len(edges)):\n",
    "        #     if not visited[i]:\n",
    "        #         dfs(i)\n",
    "        #         cnt += 1\n",
    "            \n",
    "        # return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 转换为图数据结构 领接表\n",
    "        def dfs(ind):\n",
    "            if visited[ind]:\n",
    "                return True\n",
    "            visited[ind] = True\n",
    "            for j in edge[ind]:\n",
    "                dfs(j)\n",
    "        edge = [[] for _ in range(n)]\n",
    "        for e in edges:\n",
    "            edge[e[0]].append(e[1])\n",
    "            edge[e[1]].append(e[0])\n",
    "        visited = [False] * n\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            if visited[i] or not edge[i]:\n",
    "                continue\n",
    "            count += 1\n",
    "            dfs(i)\n",
    "        \n",
    "        return count + visited.count(False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "        \n",
    "        # Initialize a set to keep track of visited nodes\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(node):\n",
    "            visited.add(node)\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    dfs(neighbor)\n",
    "\n",
    "        # Count the number of connected components\n",
    "        count = 0\n",
    "        for node in range(n):\n",
    "            if node not in visited:\n",
    "                dfs(node)\n",
    "                count += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        def dfs(node):\n",
    "            visited[node] = True\n",
    "            for neighbor in graph[node]:\n",
    "                if not visited[neighbor]:\n",
    "                    dfs(neighbor)\n",
    "        \n",
    "        graph = defaultdict(list)\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "        # print(graph)\n",
    "        visited = [False] * n\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                res += 1\n",
    "                dfs(i) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        ht=defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            ht[x].append(y)\n",
    "            ht[y].append(x)\n",
    "        def dfs(x,visit):\n",
    "            nonlocal ans\n",
    "            nonlocal ht\n",
    "            visit.add(x)\n",
    "            for m in ht[x]:\n",
    "                if m not in visit:\n",
    "                    dfs(m,visit)\n",
    "        visit=set()\n",
    "        for i in range(n):\n",
    "            if i not in visit:\n",
    "                dfs(i,visit)\n",
    "                ans+=1\n",
    "        return ans\n",
    "        \n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        #BFS\n",
    "        dic=defaultdict(list)\n",
    "        visited=set()\n",
    "        queue=[]\n",
    "        cnt=0\n",
    "        for edge in edges:\n",
    "            dic[edge[0]].append(edge[1])\n",
    "            dic[edge[1]].append(edge[0])\n",
    "        # for i in range(n):\n",
    "        #     if i not in visited:\n",
    "        #         visited.add(i)\n",
    "        #         cnt+=1\n",
    "        #         queue.append(i)\n",
    "        #         while queue:\n",
    "        #             cur=queue.pop()\n",
    "        #             for v in dic[cur]:\n",
    "        #                 if v not in visited:\n",
    "        #                     visited.add(v)\n",
    "        #                     queue.append(v)\n",
    "        #return cnt \n",
    "\n",
    "        #DFS\n",
    "        def dfs(node):\n",
    "            if node in visited:\n",
    "                return\n",
    "            visited.add(node)\n",
    "            for v in dic[node]:\n",
    "                dfs(v)\n",
    "                \n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                cnt+=1\n",
    "                dfs(i)\n",
    "                visited.add(i)\n",
    "        return cnt\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
